package com.samxcode.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find
 * all unique triplets in the array which gives the sum of zero.
 * 
 * solution:
 * 1.sort the array at the first
 * 2.for the num[K], make two pointer---the left initialized k and the right initialized num.length-1
 *   if num[k]+num[left]+num[right]<0, then update left=left+1
 *   if num[k]+num[left]+num[right]>0, then update right=right-1
 *   if the sum equals 0, then store the result
 * 
 * @author Sam
 *
 */
public class ThreeSum {

    public static void main(String[] args) {
        int[] num = { -1, -3, 4, 8, 16, 32, 64, 128 };
        System.out.println(threeSum(num));
    }


    public static List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        // sort the array
        Sort.insertSort(num);
        int font, back, sum;
        for (int i = 0; i < num.length - 2; i++) {
            // skip i when this number is same to the previous to remove duplicates
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            // impossible to find the sum if the start number is larger than 0
            if (num[i] > 0) {
                break;
            }
            font = i + 1;
            back = num.length - 1;
            while (font < back) {
                sum = num[i] + num[font] + num[back];
                if (sum < 0) {
                    // update font pointer and remove duplicates
                    do {
                        font++;
                    } while (font < back && num[font] == num[font - 1]);
                } else if (sum > 0) {
                    // update back pointer and remove duplicates
                    do {
                        back--;
                    } while (back > font && num[back] == num[back + 1]);
                } else {
                    result.add(Arrays.asList(num[i], num[font], num[back]));
                    // update the pointers and remove duplicates
                    do {
                        font++;
                    } while (font < back && num[font] == num[font - 1]);
                    do {
                        back--;
                    } while (back > font && num[back] == num[back + 1]);
                }
            }
        }
        return result;
    }

}
